1. Field of the Invention
This invention relates, in general, to a method and apparatus for decoding convolutionally-encoded signals. More specifically, the invention relates to a traceback method and apparatus for Viterbi decoding.
2. Description of the Relevant Art
Digital signal processing algorithms are characterized by repetitive accesses to data, especially at the input end of a processing chain. Decoding of convolutionally-encoded signals is a typical example of such repeating address patterns. The need for speed and compactness imposed by real-time signal processing applications often requires the use of special structures that exploit this regularity to accelerate the generation of addresses. In software, this may involve placing coefficients in memory in order of use, so that simple address increment operations can access them. Alternatively, simple hardware logic can be developed to implement address generation.
One way of achieving regular, repetitive addressing is through the use of a circular buffer. The circular buffer is used for cases in which limited amounts of data are accessed in sequence over and over. For example, filter coefficients are accessed in sequence to multiply a consecutive set of samples, and then the samples are shifted by one and the same set of filter coefficients are again accessed. The address cycle may proceed in increments of one and reset to zero after reaching a maximum value of Nxe2x88x921, thereby implementing a modulo N counter. Alternatively, the address cycle may increment by a number m greater than 1, implementing a striding memory that accesses every mth location until exceeding Nxe2x88x921, then resetting either back to zero or to the remainder of the quotient N/m. If N is an integer power of two, N=2i, a simple hardware solution can pick the least significant i bits of a counter to provide modulo N cycling. In software, simple bit masking by means of a logical AND can be used for modulo address generation.
In the Viterbi algorithm, an important set of operations is the sequence of choosing a minimum from N numbers, identifying the argmin, or index of the minimum number, adding the minimum to an accumulating distance score, and passing back the argmin and updated distance score. Typically N numbers that correspond to distance values are received and the minimum values sxe2x80x2 and the index of that minimum value, txe2x80x2, are calculated. Alternatively, the distance measure, which is small for similar patterns, could be replaced by a similarity measure, which increases as two patterns become identical, and the min function would be replaced by a max function. The minimum distance sxe2x80x2 is added to a global distance that is the accumulation of many such operations in the past from the scoring of other recognition subunits and the global distance is thus updated. The argmin is sent to a linked list structure.
Viterbi decoders are used heavily in communications applications for Forward Error Correction (FEC). They undo the encoding of convolutional encoders and correct bit errors. An essential part of the Viterbi decoder is a traceback memory (TM). It stores information about decisions made by an Add-Compare-Select Unit (ACSU). For each state of the Viterbi trellis, the TM contains a circular buffer. The ACSU writes the decision information into the TM, and a Traceback Unit reads that information from the TM and decodes the bit stream.
Heretofore, the TM required separate circular buffers for each state of the Viterbi trellis. For each buffer, a start and an end address needed to be stored. Accesses to these buffers require an address generation unit that checks for overflow and maintains the circular structure. This address generation is costly both in terms of silicon area as well as cycle count.
Accordingly, the present invention is directed to a Viterbi decoding method and apparatus that substantially obviates one or more of the problems due to limitations and disadvantages of the related art. Additional features and advantages of the invention will be set forth in the description which follows, and in part will be apparent from the description, or may be learned by practice of the invention. The objectives and other advantages of the invention will be realized and attained by the method and apparatus particularly pointed out in the written description and claims hereof, as well as the appended drawings.
To achieve these and other advantages, and in accordance with the purpose of the invention as embodied and broadly described, there is provided apparatus for Viterbi decoding of an encoded signal represented as a time-sequence of coded symbols. The apparatus includes a processor receiving the encoded signal and generating therefrom a time-sequence of trellis-state decision records; a buffer receiving and storing in an array the time-sequence of trellis-state decision records, the buffer time-sequence shifting in the array a plurality of the time-sequence of trellis-state decision records; and a traceback unit operatively connected to the buffer tracing back a path in the array representing a most-likely survivor path and generating therefrom a decoded signal.
In another aspect of the apparatus, the buffer comprises a plurality of indexed-buffer registers each storing a predetermined one of the plurality of trellis-state decision records, each such indexed-buffer register responsive to a first (GSP) and a second (WRITEP) write pointer signal; the first write pointer signal pointing to one of the plurality of indexed-buffer registers as the shifted starting point of the time-sequence array and the second write pointer signal pointing to the index within each of the buffer registers for storage of the trellis-state decision records.
In yet another aspect of the apparatus, the first write pointer is incremented by a fixed predetermined value. Also in another aspect of the apparatus, the second write pointer is incremented by a fixed predetermined value after each trellis-state decision is generated by the processor.
In another aspect of the apparatus, the buffer is further responsive to a read pointer signal (READP) generated by the traceback unit pointing to the trellis-state decision being read; the READP being formed from a state number of the trellis-state and a read base signal (RBASE).
Also in another aspect of the invention, the read base signal is decremented by a fixed predetermined value.
In another aspect of the apparatus, the memory length of indexed-buffer registers, M, is a power of 2 and wherein said second write pointer predetermined fixed incrementing value is register size N. Also in another aspect of the apparatus, the total memory length, M, is not a power of 2, and wherein said second write pointer is set to the remainder after subtracting M, if a subtraction therefrom by M produces a positive or zero result. Also in another aspect of the apparatus, the subtraction is performed by modulo (2N+1) addition of the value xe2x88x92N.
In yet another aspect of the apparatus, the buffer is a random access memory (RAM).
Also, in accordance with the invention, there is provided a method of Viterbi decoding of an encoded signal represented as a time-sequence of coded symbols, having, the steps of generating from the encoded signals a time-sequence of trellis-state decision records, storing the records in an array, generating a decoded symbol from traceback paths in the array, and shifting pointers for the records in the array.
In another aspect of the method, the array comprises a plurality of indexed-buffer registers each storing a predetermined one of the trellis-state decision records, each such indexed-buffer register responsive to a first write pointer (GSP) signal and a second write pointer (WRITEP) signal; the first write pointer signal pointing to one of the plurality of indexed-buffer registers as the shifted starting point of the time-sequence array and the second write pointer signal pointing to the index within each of the buffer registers for storage of the trellis-state decision records, wherein the shifting step comprises the steps of incrementing the first write pointer by a fixed predetermined value each time a bit is decoded, and incrementing the second write pointer by a fixed predetermined value after the trellis-state decision is generated.
In another aspect of the Viterbi decoding method, the memory length N, is a power of 2. Also, in another aspect of the method, the memory length, N is not a power of 2, wherein the second write pointer incrementation step calls for incrementing by the register size, and the time-sequence shifting step further includes the step of setting the second write pointer to the remainder after subtraction M, if a subtraction therefrom by N produces a negative result. In another aspect of the method, the subtraction is performed by modulo 2N+1 addition of the value xe2x88x92N.
Additionally, in accordance with the invention, there is provided apparatus for traceback buffer management and generation of decoded signals, length of the buffer does not have to equal (TBL). The apparatus includes a control, a traceback memory (TM) having in one embodiment a read port and a write port, and in another embodiment a read/write port, arranged as a plurality of buffers, each a predetermined length (TBL), a write address unit connected to the TM write port and responsive to the control, generating a local write pointer signal to a selected buffer in the TM; and a read address unit connected to the TM read port and responsive to the control, generating a read pointer signal for the generation of decoded signals.
In another aspect of the invention, the TM is a RAM.
In another aspect of the apparatus, the Traceback memory management apparatus further includes a global start pointer (GSP) register responsive to the control and wherein the read address unit includes a read base address (RBASE) register responsive to the control; wherein the RBASE register is decremented after each trellis-state transition is processed during trace elements and wherein the generation of a decoded signal occurs when the contents of the RBASE register equals the contents of the GSP register.
In another aspect of the apparatus, the write address unit comprises a write address register storing the write address pointer signal; a buffer length register; a first adder having an output connected to the write address register, receiving the write address pointer signal and the buffer length signal and generating therefrom an updated write address pointer signal; a write base address register storing a write base pointer signal received from the control; and a second adder having an output connected to the write base address register, receiving the write base pointer signal and the first predetermined incrementing value signal and generating therefrom an updated write base address signal, wherein the control operatively selects the local write pointer signal from the output of the write address pointer signal or the output of the write base address register.
In another aspect of the Traceback memory management apparatus wherein the value memory length is a power of 2, the read address unit further includes a read address register storing the read pointer signal; a register for left-shifting and storing a trellis-state number value; a first adder having an output connected to the read address register, receiving the read address pointer signal and receiving the shifted trellis-state signal and generating therefrom an updated read address pointer signal; a multiplexer receiving the signal stored in the write base address register and the signal stored in the read base address (RBASE) register, the control operatively selecting therefrom a signal to be generated; and a second adder having an output connected to the read base address (RBASE) register, receiving the signal generated by the multiplexer and a predetermined decrementing value signal and generating therefrom an updated read base address signal.